package exp6;


import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

// 定义一个哈夫曼树的节点类
class HuffmanNode implements Comparable<HuffmanNode> {
    char ch; // 节点对应的字符
    int freq; // 节点的权值，即字符出现的频率
    HuffmanNode left; // 节点的左子树
    HuffmanNode right; // 节点的右子树

    // 构造方法
    public HuffmanNode(char ch, int freq) {
        this.ch = ch;
        this.freq = freq;
        this.left = null;
        this.right = null;
    }

    // 实现Comparable接口，按照权值从小到大排序
    @Override
    public int compareTo(HuffmanNode o) {
        return this.freq - o.freq;
    }
}

// 定义一个哈夫曼树的类
class HuffmanTree {
    HuffmanNode root; // 哈夫曼树的根节点
    Map<Character, String> codes; // 哈夫曼编码表，存储每个字符的编码

    // 构造方法，根据字符串构建哈夫曼树
    public HuffmanTree(String str) {
        // 统计字符串中每个字符出现的频率
        Map<Character, Integer> freqMap = new HashMap<>();
        for (char ch : str.toCharArray()) {
            freqMap.put(ch, freqMap.getOrDefault(ch, 0) + 1);
        }

        // 创建一个优先队列，按照权值从小到大排序
        PriorityQueue<HuffmanNode> pq = new PriorityQueue<>();

        // 把每个字符和它的频率作为一个节点，放入优先队列中
        for (Map.Entry<Character, Integer> entry : freqMap.entrySet()) {
            pq.offer(new HuffmanNode(entry.getKey(), entry.getValue()));
        }

        // 构建哈夫曼树
        while (pq.size() > 1) {
            // 从优先队列中取出两个权值最小的节点
            HuffmanNode left = pq.poll();
            HuffmanNode right = pq.poll();

            // 创建一个新的节点，它的权值是两个子节点的权值之和
            HuffmanNode parent = new HuffmanNode('\0', left.freq + right.freq);

            // 把两个子节点作为新节点的左右子树
            parent.left = left;
            parent.right = right;

            // 把新节点放回优先队列中
            pq.offer(parent);
        }

        // 最后剩下的节点就是哈夫曼树的根节点
        root = pq.poll();

        // 生成哈夫曼编码表
        codes = new HashMap<>();
        generateCodes(root, "");
    }

    // 递归遍历哈夫曼树，生成哈夫曼编码表
    private void generateCodes(HuffmanNode node, String code) {
        // 如果节点是空的，直接返回
        if (node == null) {
            return;
        }

        // 如果节点是叶子节点，就把它的字符和编码存入哈夫曼编码表中
        if (node.left == null && node.right == null) {
            codes.put(node.ch, code);
        }

        // 如果节点有左子树，就在编码后面加上0，然后递归遍历左子树
        if (node.left != null) {
            generateCodes(node.left, code + "0");
        }

        // 如果节点有右子树，就在编码后面加上1，然后递归遍历右子树
        if (node.right != null) {
            generateCodes(node.right, code + "1");
        }
    }

    // 压缩字符串，返回压缩后的字符串
    public String compress(String str) {
        // 创建一个字符串缓冲区，用来存储压缩后的字符串
        StringBuilder sb = new StringBuilder();

        // 对字符串中的每个字符，找到它的哈夫曼编码，然后拼接起来
        for (char ch : str.toCharArray()) {
            sb.append(codes.get(ch));
        }

        // 返回压缩后的字符串
        return sb.toString();
    }

    // 解压字符串，返回解压后的字符串
    public String decompress(String str) {
        // 创建一个字符串缓冲区，用来存储解压后的字符串
        StringBuilder sb = new StringBuilder();

        // 从根节点开始遍历哈夫曼树
        HuffmanNode node = root;

        // 对压缩后的字符串中的每个字符，进行解码
        for (char ch : str.toCharArray()) {
            // 如果字符是0，就向左走
            if (ch == '0') {
                node = node.left;
            }
            // 如果字符是1，就向右走
            else {
                node = node.right;
            }

            // 如果到达了叶子节点，就输出它的字符，然后回到根节点
            if (node.left == null && node.right == null) {
                sb.append(node.ch);
                node = root;
            }
        }

        // 返回解压后的字符串
        return sb.toString();
    }
}

// 测试代码
public class HuffmanCompress {
    public static void main(String[] args) {
        // 创建一个字符串
        String str = "AACABCDCSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS";

        // 创建一个哈夫曼树
        HuffmanTree huffmanTree = new HuffmanTree(str);

        // 压缩字符串
        String compressed = huffmanTree.compress(str);
        System.out.println("Compressed: " + compressed);
        System.out.println("Compressed:" + (compressed.length() / str.length()) * 100 + "%");

        // 解压字符串
        String decompressed = huffmanTree.decompress(compressed);
        System.out.println("Decompressed: " + decompressed);
    }
}

